package com.cyy.tree;

import java.util.Comparator;

/**
 * 平衡二叉搜索树
 * 只增加了旋转操作
 * @author 会玩的洋洋
 * @since 2022-02-24
 */
public class BBST<E> extends BST<E> {

    public BBST() {
    }

    public BBST(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * 进行一次旋转操作
     * @param r
     * @param b
     * @param c
     * @param d
     * @param e
     * @param f
     */
    protected void rotate(
            Node<E> r, // 子树根节点
            Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f) {
        // 让 d 成为这棵子树的根节点
        d.parent = r.parent;
        if (r.isLeftChildren()) {
            r.parent.left = d;
        } else if (r.isRightChildren()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        // b - c
        b.right = c;
        if (c != null) {
            c.parent = b;
        }

        // e - f
        f.left = e;
        if (e != null) {
            e.parent = f;
        }

        // b - d - f
        d.left = b;
        b.parent = d;
        d.right = f;
        f.parent = d;

    }

    /**
     * 左旋转
     * @param grand 要旋转的节点 (祖父节点)
     */
    protected void leftRotate(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand, parent, child);
    }

    protected void rightRotate(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }

    /**
     * 进行修改父节点指向操作
     * @param grand 祖父节点
     * @param parent 父节点
     * @param child 子节点
     */
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        parent.parent = grand.parent;
        if (grand.isLeftChildren()) {
            grand.parent.left = parent;
        } else if (grand.isRightChildren()) {
            grand.parent.right = parent;
        } else {
            // 根节点
            root = parent;
        }
        if (child != null) {
            child.parent = grand;
        }
        grand.parent = parent;
    }
}
